package com.ds.test;

import java.io.File;

import org.apache.log4j.Logger;

import com.yuufa.util.Tool;

public class Main {
    
    public static void main(String[] args) {
        
    }
    
    public static void test() {
        
        int[] s = Tool.random(5, 50);
        Tree head = null;
        
        for(int i=0;i<s.length;i++) {
            head = insertNode(head, s[i]);
        }
        
        inorder(head);
    }
    
    public static void inorder(Tree head) {
        
        if(head != null) {
            inorder(head.getLeft());
            System.out.printf("%4d", head.getData());
            inorder(head.getRight());
        }
    }
    
    public static Tree insertNode(Tree head, int data) {
        
        if(head == null) {
            head = new Tree(data);
        } else {
            if( data > head.getData() ) {
                head.setRight( insertNode(head.getRight(), data) );
            } else if ( data < head.getData() ) {
                head.setLeft( insertNode(head.getLeft(), data) );
            }
        }
        
        return head;
    }
    
    // TODO ???
    public static Tree createBinaryTree(int n) {
        
        int[] s = Tool.random(n, 50);

        Tree head = new Tree(s[0]);
        Tree root = head;

        for (int i = 1; i < n; i++) {
            head = root;
            int data = s[i];

            while (head != null) {
                if (data > head.getData()) {
                    if(head.getRight() == null) {
                        head.setRight(new Tree(data));
                        break;
                    } else {
                        head = head.getRight();
                    }
                } else if (data < head.getData()) {
                    if(head.getLeft() == null) {
                        head.setLeft(new Tree(data));
                        break;
                    } else {
                        head = head.getLeft();
                    }
                }
            }
        }
        
        return root;
    }

    public static Node reverseList(Node head) {

        Node tail = null;
        Node q = tail;

        while (head != null) {
            q = head;
            head = head.getNext();
            q.setNext(tail);
            tail = q;
        }

        return tail;
    }

    public static Node createList() {

        int n = 5;
        int[] s = Tool.random(n);

        Node head = new Node();
        Node pointer = head;

        for (int i = 0; i < n; i++) {
            Node t = new Node(s[i]);

            pointer.setNext(t);
            pointer = pointer.getNext();
        }

        head = head.getNext();

        return head;
    }
}

class ArrayTest {
    
    public static void test() {
        int n = 20;
        int[] s = new int[100];
        int digit = 1;
        
        s[1] = 1;
        for (int i = 1; i <= n; i++) {
            
            for(int j=1;j<=digit;j++) {
                s[j] *= i;
            }
            
            for(int j=1;j<=digit;j++) {
                
                if( j == digit && s[j] >= 10 ) {
                    digit++;
                }
                
                if( s[j] >= 10 ) {
                    s[j+1] += s[j] / 10;
                    s[j] = s[j] % 10;
                }
            }
            
            for(int k=digit;k>=1;k--) {
                System.out.print(s[k]);
            }
            System.out.println();
        }
    }
}

class Directory {
    private static final Logger logger = Logger.getLogger(Directory.class);
    
    public static void test() {
        
        String path = "E:\\revamp\\";
        File file = new File(path);
        
        printHierarchy(file, 1);
    }
    
    public static void printHierarchy(File file, int level) {
        
        File[] files = file.listFiles();
        
        String space = "";
        for(int j=0;j<level;j++) {
            space += "  ";
        }
        
        for(int i=0;i<files.length;i++) {
            if( files[i].isDirectory() ) {
                System.out.println(space + files[i].getName());
                printHierarchy(files[i], level+2);
            } else {
                System.out.println(space + files[i].getName());
            }
        }
    }
}

class Gcd {
    
    public static void test() {
        int m = 28;
        int n = 18;
        
        int value = gcd(m, n);
        
        System.out.println(value + " = " + test1(m, n));
    }
    
    // m > n
    public static int test1(int m, int n) {
        
        do {
            int t = m;
            m = n;
            n = t % n;
        } while( n != 0);
        
        return m;
    }
    
    // m > n
    public static int gcd(int m, int n) {
        if( n == 0) {
            return m;
        } else {
            return gcd(n, m%n);
        }
    }
}

class Permutation {
    
    public static void test() {
        char[] s = {'a','b','c','d'};
        
        permutation(s, 0, s.length-1, s.length);
    }
    
    public static void permutation(char[] s, int first, int last, int n) {
        
        if (first == last) {
            for (int i = 0; i < n; i++) {
                System.out.print(s[i]);
            }
            System.out.println();
        } else {
            for (int i = first; i <= last; i++) {
                char t = s[i]; s[i] = s[first]; s[first] = t;
                permutation(s, first + 1, last, n);
                t = s[i]; s[i] = s[first]; s[first] = t;
            }
        }
    }
}

class Fib {
    
    public static void test() {
        
        int n = 4;
        System.out.println(fib(n) + "," + fib1(n) + "," + fib2(n));
    }
    
    public static int fib(int n) {
        
        if( n == 0 || n == 1) {
            return n;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }
    
    public static int fib2(int n) {
        
        int[] s = new int[n+1];
        s[0] = 0; s[1] = 1;
        
        for(int i=2;i<=n;i++) {
            s[i] = s[i-1] + s[i-2];
        }
        
        return s[n];
    }
    
    public static int fib1(int n) {
        
        int n0 = 0;
        int n1 = 1;
        int n2 = n1 + n0;
        
        if( n == 0 ) {
            return n0;
        } else if ( n == 1) {
            return n1;
        } else {
            for(int i=2;i<=n;i++) {
                n2 = n1 + n0;
                n0 = n1;
                n1 = n2;
            }
        }
        
        return n2;
    }
}

class Search {
    
    public static void test() {
        int n = 7;
        int[] s = Tool.random(n);
        
        int key = 41;
        Insert.sort(s, n);
        
        // int index = Search.binary(s, n, key);
        int index = Search.binary(s, 0, n-1, key);
        
        System.out.println(index);
    }
    
    public static int linear(int[] s, int n, int key) {
        
        for(int i=0;i<n;i++) {
            if(key == s[i]) {
                return i;
            }
        }
        
        return -1;
    }
    
    public static int binary(int[] s, int left, int right, int key) {
        
        if(left <= right) {
            int middle = (left + right) / 2;
            
            if(key == s[middle]) {
                return middle;
            } else if(key > s[middle]) {
                return binary(s, middle+1, right, key);
            } else if(key < s[middle]) {
                return binary(s, left, middle-1, key);
            }
        }
        
        return -1;
    }
    
    public static int binary(int[] s, int n, int key) {
        
        int left = 0;
        int right = n - 1;
        
        while(left <= right) {
            int middle = (left + right) / 2;
            
            if(s[middle] == key) {
                return middle;
            } else if(s[middle] > key) {
                right = middle - 1;
            } else if(s[middle] < key) {
                left = middle + 1;
            }
        }
        
        return -1;
    }
}

class Merge {
    
    public static void test() {
        int n1 = 4;
        int[] s1 = Tool.random(n1);
        Bubble.sort(s1, n1);
        
        int n2 = 3;
        int[] s2 = Tool.random(n2);
        Bubble.sort(s2, n2);
        
        int[] s = merge(s1, n1, s2, n2);
        
        Tool.output(s, 0, s.length-1);
    }
    
    public static int[] merge(int[] s1, int n1, int[] s2, int n2) {
        int[] s = new int[n1+n2];
        
        int i=0, j=0, k=0;
        
        while(i<n1 && j<n2) {
            if(s1[i] < s2[j]) {
                s[k++] = s1[i++];
            } else {
                s[k++] = s2[j++];
            }
        }
        
        while(i<n1) {
            s[k++] = s1[i++];
        }
        
        while(j<n2) {
            s[k++] = s2[j++];
        }
        
        return s;
    }
    
    public static void test_() {
        int n = 9;
        int[] s = Tool.random(n);
        
        // TODO
    }
    
    public static void merge(int[] s, int left, int pos, int right) {
        // TODO
    }
}

class Heap {
    
    public static void test() {
        int n = 6;
        int[] s = Tool.randomHeap(n);

        sort(s, n);

        Tool.output(s, 1, n);
    }
    
    public static void shift(int[] s, int i, int n) {
        
        int j = 2 * i;
        int t = s[i];
        
        while( j <= n ) {
            if(j<n) {
                if(s[j] < s[j+1]) {
                    j++;
                }
            }
            
            if(t < s[j]) {
                s[j/2] = s[j];
                j *= 2;
            } else {
                break;
            }
        }
        
        s[j/2] = t;
    }
    
    public static void sort(int[] s, int n) {
        
        for(int i=n/2;i>=1;i--) {
            shift(s, i, n);
        }
        
        int t = s[1]; s[1] = s[n]; s[n] = t;
        
        for(int i=n-1;i>=1;i--) {
            shift(s, 1, i);
            
            t = s[1]; s[1] = s[i]; s[i] = t;
        }
    }
}

class Quick {
    
    public static void test() {
        int n = 6;
        int[] s = Tool.random(n);

        sort(s, 0, n-1, n);

        Tool.output(s, 0, n - 1);
    }
    
    public static int partition(int[] s, int left, int right, int n) {
        int pivot = s[left];
        int i = left;
        int j = right + 1;
        
        while(i<j) {
            while(++i<=right && s[i] < pivot);
            while(--j>=left && s[j] > pivot);
            
            if(i<j) {
                int t = s[i]; s[i] = s[j]; s[j] = t;
            }
        }
        
        s[left] = s[j]; s[j] = pivot;
        
        return j;
    }
    
    public static void sort(int[] s, int left, int right, int n) {
        
        if(left <= right) {
            int k = partition(s, left, right, n);
            sort(s, left, k-1, n);
            sort(s, k+1, right, n);
        }
    }
}

class Shell {

    public static void test() {
        int n = 6;
        int[] s = Tool.random(n);

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int gap = n / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int t = s[i];
                int j = i - gap;

                while (j >= 0 && t < s[j]) {
                    s[j + gap] = s[j];
                    j -= gap;
                }

                s[j + gap] = t;
            }
        }
    }
}

class Insert {

    public static void test() {
        int n = 6;
        int[] s = Tool.random(n);

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int i = 0; i < n; i++) {
            int t = s[i];
            int j = i - 1;

            while (j >= 0 && t < s[j]) {
                s[j + 1] = s[j];
                j--;
            }
            s[j + 1] = t;
        }
    }
}

class Select {

    public static void test() {
        int n = 6;
        int[] s = Tool.random(n);

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int i = 0; i < n; i++) {
            int j = i;

            for (int k = i + 1; k < n; k++) {
                if (s[k] < s[j]) {
                    j = k;
                }
            }

            int t = s[j]; s[j] = s[i]; s[i] = t;
        }
    }
}

class Bubble {

    public static void test() {
        int n = 6;
        int[] s = Tool.random(n);

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (s[j] > s[j + 1]) {
                    int t = s[j];
                    s[j] = s[j + 1];
                    s[j + 1] = t;
                }
            }
        }
    }
}

class Tree {
    private int data;
    private Tree left;
    private Tree right;

    public Tree() {
    }

    public Tree(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Tree getLeft() {
        return left;
    }

    public void setLeft(Tree left) {
        this.left = left;
    }

    public Tree getRight() {
        return right;
    }

    public void setRight(Tree right) {
        this.right = right;
    }
}

class Node {
    private int data;
    private Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}